package com.yihaodian.search.facet.merger.impl;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

import com.yihaodian.api.search.facet.FacetNode;
import com.yihaodian.api.search.facet.FacetResult;
import com.yihaodian.api.search.facet.SearchFacetSpec;
import com.yihaodian.search.facet.merger.FacetMerger;

public class LabelASCMerger extends FacetMerger {

	/**
	 * The lexographical order do not affect by the merge operatioin,
	 * so we can do oerder and merge operatioin in the same time.
	 */
	@Override
	public FacetResult merge(List<FacetResult> facetResults,
			SearchFacetSpec spec) {
		if (facetResults == null) {
			return null;
		}
		PriorityQueue<Element> queue = 
			new PriorityQueue<Element>();
		for (FacetResult result : facetResults) {
			if (result != null && result.nodes != null && 
					result.nodes.size() > 0) {
				Element e = new Element(result);
				queue.add(e);
			}
		}
		
		List<FacetNode> nodes = new ArrayList<FacetNode>();
		int max = spec.getMax();
		if (max == 0) {
			max = Integer.MAX_VALUE;
		}
		
		/**
		 * In K-Way merge operation, it may get some facetNode with the same 
		 * label.
		 * So we use the [lastNode] to record the last received node 
		 * until a node with different label comes. 
		 * If the currentNode has the same label with lastNode, 
		 * just increase the value of the lastNode with currentNode's value, 
		 * and discard the currentNode.
		 */
		int mergeNodeCount = 0;
		FacetNode lastNode = null;
		while (mergeNodeCount <= max && queue.peek() != null) {
			Element e = queue.poll();
			FacetNode currentNode = e.node;
			if (lastNode != null && 
					currentNode.getLabel().compareTo(lastNode.getLabel())==0) {
				lastNode.value += currentNode.value;
			} else {
				 if (lastNode != null) {
					 mergeNodeCount++;
					 nodes.add(lastNode);
				 }
				 lastNode = currentNode;
			}
			
			/**
			 * Get the next label of the facetResult,  put it to priority queue
			 * for re-comparing.
			 */
			if (e.next()) {
				queue.add(e);
			}
		}
		
		if (lastNode != null) {
			nodes.add(lastNode);
		}
		
		
		FacetResult result = new FacetResult();
		result.setNodes(nodes);
		
		return result;
	}
	
	static class Element implements Comparable<Element> {
		FacetResult facetResult = null;;

		FacetNode node = null;
		int idx = 0;
		int size = 0;

		Element(FacetResult facetResult) {
			this.facetResult = facetResult;

			this.size = facetResult.getNodes().size();
			this.node = facetResult.getNodes().get(idx);
		}

		public boolean next() {
			idx++;
			if (idx >= size)
				return false;

			this.node = facetResult.getNodes().get(idx);
			return true;
		}

		@Override
		public int compareTo(Element o) {
			return node.getLabel().compareTo(o.node.getLabel());
		}
	}

}
